//给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。 
//
// 如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。 
//
// 如果有多种构造方法，请你返回任意一种。 
//
// 
//
// 示例： 
//
// 
//
// 输入：root = [1,null,2,null,3,null,4,null,null]
//输出：[2,1,3,null,null,null,4]
//解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
// 
//
// 
//
// 提示： 
//
// 
// 树节点的数目在 1 到 10^4 之间。 
// 树节点的值互不相同，且在 1 到 10^5 之间。 
// 
// Related Topics 二叉搜索树 
// 👍 34 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Java：将二叉搜索树变平衡
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P1382_BalanceABinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new P1382_BalanceABinarySearchTree().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public TreeNode balanceBST(TreeNode root) {
            if (root == null) {
                return null;
            }
            // 中序遍历得到有序数组
            List<Integer> list = new ArrayList<>();
            traverse(root, list);
            // 构造平衡搜索树
            return createBalanceBST(list, 0, list.size() - 1);
        }

        private void traverse(TreeNode root, List<Integer> list) {
            if (root == null) {
                return;
            }
            traverse(root.left, list);
            list.add(root.val);
            traverse(root.right, list);
        }

        private TreeNode createBalanceBST(List<Integer> list, int left, int right) {
            if (left > right) {
                return null;
            }
            int middle = (left + right) / 2;
            TreeNode root = new TreeNode(list.get(middle));
            root.left = createBalanceBST(list, left, middle - 1);
            root.right = createBalanceBST(list, middle + 1, right);
            return root;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
